The trend of achieving performance speedup through the use of multi-core and multi-processor architectures in computer systems, including printing systems, has gained widespread use in recent years. Multi-core and multi-processor architectures allow a number of threads belonging to one or more processes to execute in parallel across a number of CPUs, thereby reducing the overall execution time.
In order to take advantage of such parallelism, a process must typically be broken down into “tasks”. A task is a well-defined portion of the overall process to be performed on given input data to produce some output data. The tasks of a process should be largely independent and able to be executed in parallel.
The order in which tasks are executed, and the thread used to execute each task, is typically controlled by an application-level scheduler. The scheduler is executed within a multi-threaded process or application, and is typically separate to a scheduler that may be executing within an underlying operating system. When deciding which task to execute next, or with which thread to execute a task, the scheduler must often consider a several factors. For example, in a raster image processor (RIP) in a printing system, it is desirable that:
(i) the total time taken to process all pages being printed is minimised;
(ii) the processors are each well-utilised;
(iii) the time taken to output the first page being printed is minimised;
(iv) all pages are output in a regular and timely fashion; and
(v) the amount of memory used/required is minimised.
Many of these goals are conflicting. For example, minimising the total time taken to process all pages may result in an increase in the amount of memory used. It is difficult to simultaneously achieve all desired goals. Existing methods in the prior art are capable of achieving a subset of these goals, but none can claim to achieve all goals simultaneously, particularly in most, if not in all, situations.
Operating system scheduling has, and continues to be, an important and active research area in the field of computer science. An operating system scheduler must typically deal with several active processes, ensuring that each eventually completes and receives a fair amount of processor time. The main goal of an operating system scheduler is to keep the processors well-utilised while ensuring that high-priority processes are executed quickly. The only process-specific information an operating system scheduler can know is the user-specified priority of each process. The scheduler is not aware of the individual tasks making up a multi-threaded process, and therefore cannot hope to address several of the goals listed above.
Several heuristics have been developed for scheduling parallel tasks in a multi-threaded application. The tasks are typically modelled as a directed acyclic graph (DAG), in which nodes represent tasks and edges represent dependencies between tasks. The duration of each task may be estimated (prior to running the tasks).
Critical path heuristics are commonly used to determine the order in which tasks should be selected to be run. The critical path is the path through the DAG, from the first task to the last, that is the longest execution path. Critical path heuristics always attempt to execute tasks on the critical path before other tasks. List scheduling heuristics also use a DAG to perform task scheduling. However, list scheduling heuristics prioritise tasks by the number of dependencies they have, and always attempt to execute the task that has the largest number of dependencies. The goal of both critical path heuristics and list scheduling heuristics is always to reduce the total time taken to process all tasks. These heuristics don't have the ability to address the other goals listed above.
Another subclass of heuristics, commonly used in web servers, has the goal of executing individual jobs as quickly as possible. For example, first-come first-served and shortest response time heuristics prioritise jobs by their time of arrival and urgency, respectively. If jobs have specified deadlines for when their execution should complete, the earliest deadline first heuristic can be used. This heuristic simply prioritises jobs by their deadline, always giving preference to the job with the earliest deadline. This subclass of heuristics may address some of the above goals, namely a minimal time to output the first page, and regular page output. However, these heuristics are not capable of addressing all goals.
In the related area of supercomputing and grid computing, system-level scheduling is often used to balance resource utilisation and the timely completion of individual jobs. One widely used technique is known as backfill scheduling. The input typically consists of several multi-threaded processes or jobs, whose required number of processors is known. Each job also has a priority, which is typically specified by the user. The scheduler attempts to execute the jobs in order of priority. As a job can only run if the number of processors required by the job are available, the job may be delayed, and another job may be executed in its place. If there are unused processors at any given time, a lower-priority job that requires few processors may be executed. Backfill scheduling may address several of the above listed goals in some situations. However, backfill scheduling assumes that there are enough jobs available with widely-varying processor requirements in order to maintain high processor utilisation. This may not always be the case. Further, backfill scheduling does not consider dependencies between jobs, which can limit the available parallelism at any given point in time.